package com.mc.sort;

import com.mc.general.Tools;

public class ShellSort {
	public static <T extends Comparable<T>> void sort(T[] array){
		int h=1;
		int n = array.length;
		while(h<n/3) h = 3*h+1;//递增序列的选择是影响希尔排序性能的重要因素
		while(h>=1){
			for(int i=h;i<n;i++){
				for(int j=i;j>=h&&Tools.compare(array[j], array[j-h])==-1;j-=h)
					Tools.exchange(j, j-h, array);
			}
			h=h/3;
		}
	}
}
